447. Number of Boomerangs

Boomerangs回旋镖

1. Question

You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. A boomerang is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Return the number of boomerangs.

2. Examples

Example 1:

Input: points = [[0,0],[1,0],[2,0]]
Output: 2
Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]].

Example 2:

Input: points = [[1,1],[2,2],[3,3]]
Output: 2

Example 3:

Input: points = [[1,1]]
Output: 0

3. Constraints

• n == points.length
• 1 <= n <= 500
• points[i].length == 2
• -10⁴ <= x_i, y_i <= 10⁴
• All the points are unique.

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-boomerangs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

(i, j, k)中要求i与j的距离相等，且i与k的距离相等，但j和k的距离不一定相等。所以内层遍历结束后需要将hashmap置空。

外层循环遍历i，内层遍历i后面的数，找到和i距离相同的数，由此找到升序的可能性。

假设在第n遍外层遍历中，内层遍历寻找到m个数和n距离相同，题目则转换成m个数中选两个数可能性的问题。

任选两个数，并且这两个数升序排序的结果有(1+2+...+(n-1))种

答案有ijk和ikj两种，因此ans*2即为结果。

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int ans = 0;
        int n = points.length;
        for (int i = 0; i < n; i++) {
            HashMap<Integer, Integer> map = new HashMap();
            for (int j = 0; j < n; j++) {
                int a = points[i][0] - points[j][0];
                int b = points[i][1] - points[j][1];
                int dist = a * a + b * b;
                Integer val = null;
                if ((val = map.get(dist)) == null) {
                    map.put(dist, 1);
                } else {
                    ans += val;
                    map.put(dist, val + 1);
                }
            }
        }
        return ans * 2;
    }
}